#pragma once

#include <algorithm>
#include <vector>

namespace solution_039
{

class Solution
{
public:
    std::vector< std::vector<int> > combinationSum(std::vector<int>& candidates, int target)
    {
        std::sort(candidates.begin(), candidates.end());

        std::vector< std::vector<int> > combs;
        std::vector< std::pair<int, int> > stack{{0, 0}};
        int stack_sum = 0;

        while (!stack.empty()) {
            auto id = stack.back().second++;
            if (stack_sum + candidates.at(id) < target) {
                stack.emplace_back(candidates.at(id), id);
                stack_sum += candidates.at(id);
            } else {
                if (stack_sum + candidates.at(id) == target) {
                    combs.emplace_back();
                    for (auto it = stack.cbegin() + 1; it != stack.cend(); ++it)
                        combs.back().push_back(it->first);
                    combs.back().push_back(candidates.at(id));
                }
                stack_sum -= stack.back().first;
                stack.pop_back();
                while (!stack.empty() && stack.back().second == (int)candidates.size()) {
                    stack_sum -= stack.back().first;
                    stack.pop_back();
                }
            }
        }

        return combs;
    }

    std::vector< std::vector<int> > combinationSum2(std::vector<int>& candidates, int target)
    {
        std::vector< std::vector<int> > combs;
        std::vector< std::pair<int, int> > stack{{0, 0}};
        int stack_sum = 0;

        while (!stack.empty()) {
            auto id = stack.back().second++;
            if (stack_sum < target) {
                stack.emplace_back(candidates.at(id), id);
                stack_sum += candidates.at(id);
            } else {
                if (stack_sum == target) {
                    combs.emplace_back();
                    for (auto it = stack.cbegin() + 1; it != stack.cend(); ++it)
                        combs.back().push_back(it->first);
                }
                stack_sum -= stack.back().first;
                stack.pop_back();
                while (!stack.empty() && stack.back().second == (int)candidates.size()) {
                    stack_sum -= stack.back().first;
                    stack.pop_back();
                }
            }
        }

        return combs;
    }

    std::vector< std::vector<int> > combinationSum3(std::vector<int>& candidates, int target)
    {
        std::sort(candidates.begin(), candidates.end());
        m_candi = &candidates;
        std::vector<int> path;
        backtrack(path, 0, target);
        return m_comb;
    }

private:
    void backtrack(std::vector<int>& path, int first, int target)
    {
        if (target == 0) {
            m_comb.push_back(path);
            return;
        }

        for (int i = first; i < (int)m_candi->size() && target >= m_candi->at(i); ++i) {
            path.push_back(m_candi->at(i));
            target -= m_candi->at(i);
            backtrack(path, i, target);
            path.pop_back();
            target += m_candi->at(i);
        }
    }

    const std::vector<int>* m_candi;
    std::vector< std::vector<int> > m_comb;
};

}  /* namespace solution_039 */
